/*You are given N unique numbers a1<a2<a3<...an. Find out the count of all possible binary search tress that can be constructed using these numbers.
for example with 3 elements 1,2,3 there are 5 possible BST and for 1,2,3,4 there are 14 bst
*/

#include<stdio.h>
#include<conio.h>
#include<iostream.h>
int countTree(int noOfNode)
{
    if(noOfNode == 0 || noOfNode == 1)
       return 1;
    else
    {
        int sum = 0, left = 0, right = 0;
        for(int root = 1; root <= noOfNode; root++)
        {
                left = countTree(root-1);
                right = countTree(noOfNode - root);
                sum = sum + left * right;
        }
        return (sum);
    }
}
int main()
{
    int noOfNode, treeCount;
    cin>>noOfNode;
    treeCount =  countTree(noOfNode);
    cout<<treeCount;
    getch();
    return 0;
}
